#include"cds_rbtree.h"
#include"cds_common.h"
#include"cds_list.h"
#include<stdio.h>
#include<stdlib.h>



#ifdef __cplusplus
extern "C"{
#endif

//  如果CHECK_RB_TREE_BALANCE 为1,则在每一次删除一个数据时都会前后两次检测红黑树是否平衡 
#define CHECK_RB_TREE_BALANCE 0

static void __left_rotate(rbtree_t * tree, rbnode_t * p, rbnode_t * c);
static void __right_rotate(rbtree_t * tree,rbnode_t * p, rbnode_t * c );
static void __balance_for_insert(rbtree_t * tree, rbnode_t * cur_node );
static void __balance_for_del(rbtree_t * tree, rbnode_t * node );
static int __get_levels(rbnode_t * node );

#define RB_RED 0x0 
#define RB_BLACK 0x1
#define get_parent(node)  ((rbnode_t *)((node)->parent_color&0xfffffffffffffff8))

#define set_parent(node,parent) do{\
    ((node)->parent_color = (node)->parent_color&0x7|(unsigned long)parent);\
}while(0)

#define get_brother(node) ({\
    rbnode_t * _parent = get_parent(node);\
    _parent?_parent->left==node? _parent->right : _parent->left:NULL;\
})

#define get_color(node) ((node)?(node)->parent_color&0x7:RB_BLACK)

#define is_red_color(node) (get_color(node) == RB_RED ) 

#define is_black_color(node) (get_color(node) == RB_BLACK ) 

#define set_color(node,color) ((node)->parent_color = (node)->parent_color&0xfffffffffffffff8|color)

#define set_red_color(node) set_color(node,RB_RED) 

#define set_black_color(node) set_color(node, RB_BLACK)


//清零新节点,很有必要哦!
#define rbtree_clear_node(node) do{\
    set_parent(node,NULL);\
    set_color(node,RB_RED);\
    node->left = NULL;\
    node->right = NULL;\
}while(0);

//删除一个叶子节点的动作,根节点除外
#define rbtree_del_leaf(leaf) do{\
    rbnode_t * _parent = get_parent(leaf);\
    if(_parent->left == (leaf) )\
        _parent->left = NULL; \
    else \
        _parent->right = NULL;\
}while(0)


/* 
 * 交换两个节点的所有字段，及相关联的指针域更新
 * 
 *      相关的指针域有:
 *          其父节点的left或right指针之一,
 *          其左子节点的parent指针,
 *          其右子节点的parent指针
 *          如果没有父节点，则tree的root指针要更新
 */
#define rbtree_exchange_two_nodes(tree,n1,n2) do{\
    unsigned long _tmp;\
    for(int i=0;i<sizeof(rbnode_t)/sizeof(unsigned long);i++){\
        _tmp = ((unsigned long *)n1)[i];\
        ((unsigned long *)n1)[i] = ((unsigned long *)n2)[i];\
        ((unsigned long *)n2)[i] = _tmp;\
    }\
    rbnode_t * _arr[] = {n1,n2};\
    for(int i=0;i<2;i++){\
        rbnode_t * _it = _arr[i];\
        if(_it->left){\
            if(_it->left==_it){\
                _it->left = _arr[1-i];\
            }else{\
                set_parent(_it->left, _it);\
            }\
        }\
        if(_it->right){\
            if(_it->right==_it){\
                _it->right = _arr[1-i];\
            }else{\
                set_parent(_it->right,_it);\
            }\
        }\
        rbnode_t * parent = get_parent(_it);\
        if(parent){\
            if(parent==_it){\
                set_parent(_it,_arr[1-i]);\
            }else{\
                if( _arr[1-i] ==parent->left)\
                    parent->left = _it;\
                else \
                    parent->right = _it;\
            }\
        }else{\
            tree->root = _it;\
        }\
    }\
}while(0)


/*
 * 插入
 *  
 *  分析: 
 *      假设C(current)表示当前节点,P表示C的父节点,G表示C的祖父节点,U表示C的叔父节点。
 *      r表示红,b表示黑
 *
 *      一个新节点默认是红色,因为如果是黑色，则插在哪里都直接改变了子树的高度从而导致不平衡发生,
 *
 *      红黑树插入的4种情形
 *
 *      （1）新节点位于根节点，其没有父节点时，处理思路：将该节点直接设为黑色即可
 *
 *      （2）新节点的父节点已然是黑色时，处理思路：不用动，这已然是一颗红黑树
 *
 *      （3）父节点和叔节点都是红色时，处理思路：
 *              a.将父节点和叔节点设为黑色;
 *              b.将祖父节点设为红色;
 *              c,如果祖父节点是树的根节点，则着回黑色，整棵树的高度增加一层,否则将
 *                祖父节点设为当前节点，并继续对新当前节点进行操作
 *                   G(b)      变色       G(r)
 *                  /    \     --->      /   \
 *                 P(r)  U(r)          P(b)  U(b)
 *                /                    /
 *               C(r)                 C(r)
 *              
 *
 *      （4）父节点是红色，叔节点是黑色( 叔父节点是NULL的情况也是黑色)时，又分如下四种情况：
 *             a: LL       | b: LR    | c: RR       | d: RL
 *                      G  |       G  |       G     |       G
 *                     /   |      /   |        \    |        \
 *                    P    |     P    |         P   |         P
 *                   /     |      \   |          \  |        /
 *                  C      |       C  |           C |       C
 *                         |          |             |
 *              上边这四种情况中:  LL和RR成镜像操作,  LR和RL成镜像操作
 *
 *              LL情况的处理:   G-P 右旋, P和G交换颜色
 *              LR情况的处理:   P-C 左旋, 变成了LL的情况 
 *              RR情况的处理:   G-P 左旋, P和G交换颜色，
 *              RL情况的处理:   P-C 右旋, 变成了RR的情况
 *
 *  
 */


/*
 * 插入函数, 注意函数中的注释(1,2,3,4)
 */
rbnode_t * rbtree_insert(rbtree_t * tree, rbnode_t * node ){
    //清零新节点 
    rbtree_clear_node(node);
    // 1, 新节点位于根节点,直接染黑即可
    if(!tree->root){
        tree->root = node;
        set_color(node,RB_BLACK );
        tree->size++;
        return NULL;
    }

    unsigned long key = tree->keygen_func(node);
    rbnode_t * parent = tree->root; 
    //定位父节点并插入
    while(1){
        unsigned long pkey = tree->keygen_func(parent);
        if( key < pkey ){
            if( !parent->left ){
                parent->left = node;
                set_parent(node, parent);
                tree->size++;
                break;
            }
            parent = parent->left;
        }else if (key > pkey ){
            if( !parent->right ){
                parent->right = node;
                set_parent(node,parent);
                tree->size++;
                break;
            }
            parent = parent->right;
        }else{
            debug("相同key的数据节点已经存在，不能再插入,直接返回了这个已存在的节点\n");
            return parent;//相同key的节点已经存在，不能插入，直接返回这个节点
        }
    }
    
    // 2, 父节点是黑色,将新节点染成红色,直接插入即可
    if( is_black_color(parent) ){
        //新节点默认是红色的，所以不需要再次染红
        //set_red_color(node);
        return NULL;    
    }
    //针对第3种和第4种情况进行平衡操作
    __balance_for_insert(tree, node); 
    return NULL;
}

/*
 * 删除函数:  node参数为待删节点
 */
void rbtree_del(rbtree_t * tree, rbnode_t * node ){
    //debug("into rbtree_del: node:%p,node.color:%d, node.left:%p,node.right:%p\n",node,get_color(node),node->left,node->right);
    //如果node节点有两个子节点，则需要将它换到左子树的最大节点位置,也可以换到右子树的最小节点位置
    if(node->left && node->right ){
        rbnode_t * left_last = rbtree_last(node->left);//左最大位置
        rbtree_exchange_two_nodes(tree,node,left_last);
        //debug("node:%p,node.color:%d, node.left:%p,node.right:%p\n",node,get_color(node),node->left,node->right);
    }
    rbnode_t * parent = get_parent(node); 
    //debug("call rbtree_check_balance...\n");
#if CHECK_RB_TREE_BALANCE
    rbtree_check_balance(tree);
#endif
    //如果待删节点是叶子节点
    if(!node->left&&!node->right ){
        //如果是根节点,要更新tree->root指针
        if(tree->root==node){
            tree->root = NULL;
        }else{
            //如果要删除的叶子节点是黑色的
            if(is_black_color(node)){
                __balance_for_del(tree,node);       
            }
            //删除叶子节点
            rbtree_del_leaf(node);
        }
        
    }
    //待删节点只有一个子树的情况 ,待删节点一定是黑,其子节点一定是红 
    else{
        rbnode_t * new_child =  (rbnode_t*)((unsigned long)node->left + (unsigned long)node->right );
        set_parent(new_child, parent);
        if(parent){
            if(parent->left==node){
                parent->left = new_child;
            }else{
                parent->right = new_child; 
            }
        }else{
            tree->root = new_child;
        }
        set_black_color(new_child);
    }
    //debug("call rbtree_check_balance...\n");
#if CHECK_RB_TREE_BALANCE
    rbtree_check_balance(tree);
#endif
    tree->size--;
}

//检测平衡函数
void rbtree_check_balance(rbtree_t * tree){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return ;
    }
    struct list_head head = LIST_HEAD_INIT(head);

    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(rbnode_t *));
    *(rbnode_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;
    list_add_head(new,&head);
    int new_level_flag = 1;
    int sub_nr = 1;
    int nr;
    int level=0;
    int black_levels=-1;
    while(!list_is_empty(&head)){
        if(new_level_flag){
            level++;
            new_level_flag = 0;
            nr = sub_nr;
            sub_nr = 0;
        }
        nr--;
        if(nr==0){
            new_level_flag = 1;
        }
        struct list_head * out_node = list_del_last(&head);
        rbnode_t * node = *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head));
        if(node->left){
            sub_nr++;
            *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head)) = node->left; 
            list_add_head(out_node,&head);
            out_node = NULL;  
        }
        if(node->right){
            sub_nr++;
            if(!out_node){
                out_node = malloc(sizeof(struct list_head)+sizeof(rbnode_t *));
            }
            *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head)) = node->right; 
            list_add_head(out_node,&head);
            out_node = NULL;
        }
        if(!node->left || !node->right){
            int lev = __get_levels(node);
            if(black_levels==-1)
                black_levels = lev;
            else{
                assert(lev == black_levels); 
                if(is_red_color(node))
                assert( is_black_color(get_parent(node)));
            }

        }
        if(out_node){
            free(out_node);
        }
    }
}

//搜索
rbnode_t * rbtree_search(rbtree_t * tree, unsigned long key ){
    if( !tree->root )return NULL;
    for(rbnode_t * node = tree->root;node;){
        unsigned long nkey = tree->keygen_func(node);
        if(key < nkey ){
            //debug("遇到%lu,左拐\n",nkey); 
            assert(node!=node->left);
            node = node->left;
        }else if( key > nkey ){
            //debug("遇到%lu,右拐\n",nkey); 
            assert(node!=node->right);
            node = node->right;
            
        }else{
            //debug("遇到%lu,找到了\n",nkey); 
            return node;
        }
    }
    debug("没找到\n");
    return NULL;
}

//中序遍历
void rbtree_travel_middle(rbtree_t * tree, travel_func_t travel){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    rbnode_t * node = rbtree_first(tree->root);
    while(node){
        printf(" [");
        travel(node);
        printf("]");
        node = rbtree_next(node);
    }
    printf("\n");
}

//层次遍历
void rbtree_travel_level(rbtree_t * tree, travel_func_t travel){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    struct list_head head = LIST_HEAD_INIT(head);

    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(rbnode_t *));
    *(rbnode_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;
    list_add_head(new,&head);
    int new_level_flag = 1;
    int sub_nr = 1;
    int nr;
    int level=0;
    while(!list_is_empty(&head)){
        if(new_level_flag){
            level++;
            new_level_flag = 0;
            nr = sub_nr;
            sub_nr = 0;
            printf("\n---第%d层:一共有%d个节点-----------------------------------------------------------\n",level,nr);
        }
        nr--;
        if(nr==0){
            new_level_flag = 1;
        }
        struct list_head * out_node = list_del_last(&head);
        rbnode_t * node = *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head));
        if(node->left){
            sub_nr++;
            *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head)) = node->left; 
            list_add_head(out_node,&head);
            out_node = NULL;  
        }
        if(node->right){
            sub_nr++;
            if(!out_node){
                out_node = malloc(sizeof(struct list_head)+sizeof(rbnode_t *));
            }
            *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head)) = node->right; 
            list_add_head(out_node,&head);
            out_node = NULL;
        }
        printf(" %c[",get_color(node)==RB_RED?'R':'B');
        travel(node);
        printf("] ");
        if(out_node){
            free(out_node);
        }
    }
}

//清空
void rbtree_clear(rbtree_t * tree, destroy_func_t destroy ){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    struct list_head head = LIST_HEAD_INIT(head);
    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(rbnode_t *));
    *(rbnode_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;

    list_add_head(new, &head);
    while(!list_is_empty(&head)){
        struct list_head * out_node = list_del_last(&head);
        rbnode_t * node = *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head));
        if(node->left){
            *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head)) = node->left; 
            list_add_head(out_node,&head);
            out_node = NULL;  
        }
        if(node->right){
            if(!out_node){
                out_node = malloc(sizeof(struct list_head)+sizeof(rbnode_t *));
            }
            *(rbnode_t **)(((char *)out_node)+sizeof(struct list_head)) = node->right; 
            list_add_head(out_node,&head);
            out_node = NULL;
        }
        if(out_node){
            free(out_node);
            out_node = NULL;
        }
        destroy(node);
        tree->size--;
    }
    tree->root = NULL;
}

//获取后继
rbnode_t * rbtree_next(rbnode_t * node ){
    if(node->right)
        return rbtree_first(node->right);
    for(rbnode_t * parent = get_parent(node);parent; node = parent, parent = get_parent(parent) ){
        if(parent->left == node)return parent;
    }
}

//获取前驱
rbnode_t * rbtree_prev(rbnode_t * node ){
    return node->left?rbtree_last(node->left):NULL;
}

//****************************************************************************
//** the static functions   definition ***************************************
//****************************************************************************

/**
 *   删除时要调用的平衡函数,node为待删节点,只有node为黑色的叶子节点时才调用本方法
 */
static void __balance_for_del(rbtree_t * tree, rbnode_t * node ){
    rbnode_t * d = node;
    rbnode_t * p = get_parent(d);
    rbnode_t * s = get_brother(d);
    for(int i=0;;i++){
    /*
    debug("p:%p,p.color:%d,p.left:%p,p.right:%p\n",p,get_color(p),p->left,p->right);
    debug("d:%p,d.color:%d,d.left:%p,d.right:%p\n",d,get_color(d),d->left,d->right);
    if(s){
        debug("s:%p,s.color:%d,s.left:%p,s.right:%p\n",s,get_color(s),s->left,s->right);
        if(s->left){
            debug("sl:%p,sl.color:%d,sl.left:%p,sl.right:%p\n",s->left,get_color(s->left),s->left->left,s->left->right);
        }
        if(s->right){
            debug("sr:%p,sr.color:%d,sr.left:%p,sr.right:%p\n",s->right,get_color(s->right),s->right->left,s->right->right);
        }
    }
        debug("循环第%d次\n",i);
    */
        //s为红色时，处理成黑色
        if( is_red_color(s) ){
            debug("s为红,先处理成黑\n");
            if(p->right==s){
                /*   P(b)       P-S左旋       S(r)      s,p变色  S(b)
                 *  /    \    -------->      /   \    -------->  /  \  
                 * D(b)  S(r)              P(b)  n(b)           P(r) n(b)
                 *      /   \             /   \                /   \           * 
                 *    m(b)  n(b)        D(b)  m(b)           D(b)  m(b)
                 */   
                __left_rotate(tree,p,s);
            }else{
                /*       P(b)       P-S右旋     S(r)                   S(b)
                 *      /    \     ------->    /    \      ----->      /  \
                 *     S(r)  D(b)             m(b)   P(b)             m(b) P(r)
                 *    /   \                         /  \                  /  \
                 *   m(b) n(b)                     n(b) D(b)             n(b) D(b)  
                 */
                __right_rotate(tree,p,s);
            }
            set_black_color(s);
            set_red_color(p);
            s = get_brother(d);
        }

        //接下来s一定为黑色 
        if( p->left==d && s->left && is_red_color(s->left) ){
            debug("情况A\n");
            /* 
             *  情况A:  s为黑,  d为p的左子节点，s的左子节点存在
             *
             *  说明:  如果D是正要删除的叶子节点，则e和f一定为空,因为删之前P子树是平衡的
             *         如果D是第一次处理之后的一棵平衡子树，但P树不平衡,因为D这个分支还
             *         少一个黑色节点,所以D子树下边可能还有另外的黑色节点,所以e和f就存在了
             *
             *      P(x)                P(x)                       m(r)      m着P的颜色,         m(x)
             *     /   \    S,m右旋    /   \        P,m 左旋      /    \       P着黑色          /    \ 
             *    D(b) S(b) ------>  D(b)   m(r)    -------->  P(x)    S(b)   ----------->   P(b)     S(b)  ----> 
             *        /  \                 /  \                 / \    /  \                  /  \     /   \ 
             *       m(r) n(r)?           e?   S(b)           D(b) e? f?  n(r)?             D(b) e?   f?  n(r)? 
             *      /  \                       /  \                                      
             *     e?   f?                    f?  n(r)?
             * */      
             __right_rotate(tree,s,s->left);
             __left_rotate(tree,p,p->right);
             set_color(get_parent(p),get_color(p));
             set_black_color(p);
        }else if( p->left==d && s->right && is_red_color(s->right) ){
            debug("情况B\n");
            /*
             *  情况B:  s为黑,d为p的左子节点, s的左子节点不存在，但右子节点存在
             *
             *      P(x)                        P(x)                   S(r)      S着P的豢色,    S(x)
             *     /  \         S,n换色        /   \       P,S左旋     /  \      P着黑色        /  \
             *    D(b) S(b)   --------->      D(b)  S(r)  -------->  P(x)  n(b)  -------->    P(b)  n(b)
             *          \                            \               /                        /
             *          n(r)                         n(b)           D(b)                     D(b) 
             * */      
            set_red_color(s);
            set_black_color(s->right);
            __left_rotate(tree,p,s);
            set_color(s,get_color(p));
            set_black_color(p);
        }else if( p->right==d && s->right && is_red_color(s->right)){
            debug("情况C\n");
            /*
             *  情况C(和情况A互为镜像): s为黑, d为p的右子节点, s的右子节点存在   
             *
             *      P(x)
             *     /  \
             *    S(b) D(b)
             *   /  \
             * n(r)? m(r)
             *       /  \
             *      e?   f?
             *
             * */      
            __left_rotate(tree,s,s->right);
            __right_rotate(tree,p,p->left);
            set_color(get_parent(p),get_color(p));
            set_black_color(p);
            break;
        }else if( p->right==d && s->left && is_red_color(s->left)){
            debug("情况D\n");
            /*
             *  情况D(和情况B互为镜像): s为黑, d为p的右子节点, s的右子节点不存在,但左子节点存在
             *
             *      P(x)                                            S着P的颜色,
             *     /  \       S,n换色               P,S右旋         P着黑色
             *    S(b) D(b)  ------>      ....    --------->  ....  ------->         .... 
             *   /  
             * n(r) 
             *
             */
            set_black_color(s->left);
            set_red_color(s);
            __right_rotate(tree,p,s);
            set_color(s,get_color(p));
            set_black_color(p);
            break;
        }else{
           if(is_red_color(p) ){
                debug("情况E\n");
                
               /*
                *  情况E: s为黑,s没有子节点, p为红
                *             
                *      P(r)                   P(b)
                *     /  \     -------->      /  \              
                *    D(b) S(b)               D(b) S(r)
                */
                set_black_color(p);
                set_red_color(s);
           }else{
                debug("情况F\n");
               /*
                *  情况F:  s为黑, s没有子节点,或两个子节点全为黑, p为黑
                *
                *    P(b)     S着红色        P(b)
                *   /  \      -------->     /   \    ---(如果P不是树根节点,则以P节点充当D节点继续往树根的方向处理,即循环继续)-----> *  
                *  D(b) S(b)              D(b)  S(r)
                *
                */
                set_red_color(s);
                //如果p不是根节点
                if(p!=tree->root){
                    d = p;
                    p = get_parent(d);
                    s = get_brother(d);
                    continue;
                }
           }
        }
        break;
    }
    /*
    debug("p:%p,p.color:%d,p.left:%p,p.right:%p\n",p,get_color(p),p->left,p->right);
    debug("d:%p,d.color:%d,d.left:%p,d.right:%p\n",d,get_color(d),d->left,d->right);
    if(s){
        debug("s:%p,s.color:%d,s.left:%p,s.right:%p\n",s,get_color(s),s->left,s->right);
        if(s->left){
            debug("sl:%p,sl.color:%d,sl.left:%p,sl.right:%p\n",s->left,get_color(s->left),s->left->left,s->left->right);
        }
        if(s->right){
            debug("sr:%p,sr.color:%d,sr.left:%p,sr.right:%p\n",s->right,get_color(s->right),s->right->left,s->right->right);
        }
    }
    */
}


static int __get_levels(rbnode_t * node ){
    int ret=0;
    while(node){
        if(is_black_color(node))ret++;
        node=get_parent(node);
    }
    return ret;
}

/* 
 * 左旋:  参照cds_avl.c中的__left_rotate函数的说明 
 * */
static void __left_rotate(rbtree_t * tree, rbnode_t * p, rbnode_t * c){
    debug("左旋---\n"); 
    rbnode_t * g = get_parent(p); 
    if(g){
        if(g->left == p){
            g->left = c;
        }else{
            g->right = c; 
        }
    }else{
        tree->root = c;
    }
    set_parent(c,g);
    set_parent(p,c);
    p->right = c->left;
    c->left = p;
    if(p->right){
        set_parent(p->right,p);
    }
}

/* 
 * 右旋:  参照cds_avl.c中的__right_rotate函数的说明 
 *   
 */
static void __right_rotate(rbtree_t * tree,rbnode_t * p, rbnode_t * c ){
    debug("右旋---\n");
    rbnode_t * g = get_parent(p);
    if(g){
        if(g->left == p ){
            g->left = c;   
        }else{
            g->right = c;
        }
    }else{
        tree->root = c;
    }
    set_parent(c,g);
    set_parent(p,c);
    p->left = c->right;
    c->right = p;
    if(p->left){
        set_parent(p->left,p);
    }
}

/**
 *  插入后要调用的平衡函数:
 *      cur_node:  表示当前节点，只有当前节点及其父节点均为红色时才需要调用本函数来做平衡处理
 */
static void __balance_for_insert(rbtree_t * tree, rbnode_t * cur_node ){
    
    rbnode_t * c = cur_node;
    rbnode_t * p = get_parent(c);
    rbnode_t * g = get_parent(p);
    rbnode_t * u = get_brother(p); 
    for(int i=0;;i++){
        if( is_red_color(p) && is_red_color(u) ){
            // 第3种情况: p是红,u是红,则g一定是黑,否则插入之前就违背了父子节点不能同为红的这一性质
            set_black_color(p);
            set_black_color(u);
            //如果g是根节点，则整棵树达到了平稀
            if(g==tree->root){
                break;
            }
            set_red_color(g);
            //g变成红色之后:
            //  如果g的父节点为黑色，则整棵树达到了平衡,结束循环;
            //  否则g和g的父节点同为红的情况又违背红黑树的性质，则需要继续进行平衡操作，即把g当c来继续下次循环 
            if(is_black_color(get_parent(g))){
                break;
            }
            c = g;
            p = get_parent(g);
            g = get_parent(p);
            u = get_brother(p);
        }else{
            // 第4种情况, p是红, u是黑, g是黑
            /*  LL:
            
                    G(b)      右旋       P(r)           着色        P(b)
                   /    \     --->      /   \         ------->     /    \ 
                  P(r)  U(b)          C(r)  G(b)                  C(r)  G(r)
                 /  \                       /   \                       /  \         *
                C(r) x                     x     U(b)                  x   U(b)
            */
            if(c==p->left && p==g->left){
                //s1: p,g右旋
                __right_rotate(tree,g,p);
                //s2: p着黑色,g着红色
                set_black_color(p);
                set_red_color(g);
            }
            /*  LR:
                          P,C左旋(变成了LL的情形)            
                    G(b)      ---->       G(b)     
                   /    \                /   \                                        * 
                  P(r)  U(b)          C(r)  U(b)
                 /  \                 /                 
                x   C(r)            P(r)                    
                                    /
                                   x 
            */
            else if(c==p->right && p==g->left){
                //s1: p,c左旋
                __left_rotate(tree,p,c);
                //s2: 变成了LL的情况,g,c右旋
                __right_rotate(tree,g,c);
                //s3: c,g 换色
                set_black_color(c);
                set_red_color(g);
            }
            // RR: 操作参照LL的操作作镜像改变(即左旋的镜像操作就是右旋) 
            else if( c==p->right && p==g->right){
                //s1: p,g左旋
                __left_rotate(tree,g,p);
                //s2: p,g换色
                set_black_color(p);
                set_red_color(g);
            }
            // RL: 操作参照LR的操作作镜像改变
            else{
                //s1: p,c右旋
                __right_rotate(tree,p,c);
                //s2: 变成RR, g,c 左旋
                __left_rotate(tree,g,c);
                //s3: c,g换色
                set_black_color(c);
                set_red_color(g);
            }
            break;
        }
    }
}
#ifdef __cplusplus
}
#endif
